% This is a latex file. It can also be read as a text file.
\documentstyle{article}\begin{document}
\parindent 0pt                  %no indent in first line of paragraph
\parskip .7em                   %vskip between paragraphs
\title{\bf 
        ELK EXTENSIONS TUTORIAL
}
\author{
        J.P.Lewis\\
        NEC C\&C Research\\
        zilla@ccrl.nj.nec.com
}

\date{November 13, 1992 (1)}

\maketitle

This document describes several extensions to Elk scheme:
\begin{enumerate}
\item
   A foreign function interface, currently available for Sparc and SGI 
   machines only. The author can probably provide some hints on porting
   to other machines.
\item
  `Elk Shell', i.e, a set of (mostly foreign function) bindings to 
   O/S routines which permit Elk to be used as an excellent shell 
   programming language.
\item
   Elk vector extensions, or `APL in Scheme'.  This extension permits
   fairly efficient numerical (and in particular floating point) computation
   in Scheme, despite the fact that Elk is an interpreter.
\end{enumerate}

\section{Elk Shell}

\subsection{Advertisement}

The Elk Shell syntax for simple shell commands is less convenient than 
that of the sh,csh, and Perl.  The construction of complex commands,
however, is more consistent, simpler, and more `powerful' than 
in shells such as sh,csh, and Perl; complex commands are composed
using Scheme's simple rules.
Shell languages often have a ``syntax wall: 
excess syntax is introduced to make simple operations convenient, 
but the syntax does not combine easily--
composing complex operations requires confusing combinations
of escaping, dereferencing, quoting, and other operators.
Expressions begin to look something like
\begin{verbatim}
    "'\$\\{ABC}'"
\end{verbatim}

Scheme has minimal syntax and a simple and consistent means of composing 
functions, with the result that simple constructs are perhaps more verbose,
but complex constructs are much simpler.
Important operations are easily abstracted and saved in 
libraries for later reuse.
Scheme provides considerable `cognitive economy', 
since with some effort it can be used for many of the
tasks addressed by separate and syntactically confusing tools such as
sh,csh,Perl,awk, and find.

The following is an example of a subroutine in Perl:
\begin{verbatim}
    sub arrayadd {
      local(*a, *b) = @_;
      local($max) = $#a > $#b ? $#a : $#b;
      local(@sum);
      for (local($i) = 0; $i <= $max; $i++) {
        $sum[$i] = $a[$i] + $b[$i];
      }
      @sum;
    }
    @foo = (1,2,3);
    @bar = (10,20,30);
    @totals = &arrayadd(*foo, *bar);
\end{verbatim}
The Perl code has the typical ``little language'' symptom of
excessive syntax.  This example requires the characters
{\tt *,\$,\#,@,\&} as well as parentheses, brackets and curly braces.

The corresponding Scheme is:
\begin{verbatim}
    (define (arrayadd a b)   (map + a b))

    (define foo '(1 2 3))
    (define bar '(10 20 30))
    (define totals (arrayadd foo bar))
\end{verbatim}

\subsection{Constructing an Elk Shell}

An elk shell file begins with an interpreter path such as
\begin{verbatim}
    #! /usr/local/bin/elk
\end{verbatim}
(Elk ignores this line);
the remainder of the shell file contains Scheme function calls.

The Elk call
\begin{verbatim}
    (apropos "os-") 
\end{verbatim}
prints a list of the pre-linked shell-related functions.
Many of these functions are simply the corresponding C library function
exported to Elk.  For example, Elk shells can read and write
binary data using {\tt os-fopen, os-fread, os-fwrite, os-fclose}.
Other shell-related functions are written specifically for scheme.
For example, {\tt os-glob}
returns a list of the filenames matching the specified pattern,
using a shell-like match:
\begin{verbatim}
    (os-glob "*.h")  => ("scheme.h" "object.h")
\end{verbatim}
Glob was the name of an old name matching routine. You can of
course rename functions in your Elk startup if you wish, e.g.,
\begin{verbatim}
    (define os-file* os-glob)
\end{verbatim}

The shell functions os-bsh and os-csh execute a command string
using the Bourne- and C-shells respectively, 
and return the exit status of the command.
os-bsh and os-csh are inconvenient primitives; a string representation
of each command and its arguments must be assembled.

Other more convenient functions can be built using these primitives, however.
The library file scm/shell.e includes several possible approaches
to a more convenient shell syntax.  {\tt declare-shell } is one approach
in which the shell command appears as a scheme function, while
the command arguments are scheme function arguments which should evaluate
to strings.
Examples of calling ls:
\begin{verbatim}
    (os-csh "ls /etc")          ; primitive way

    (load "shell.e")
    (declare-shell ls) 
   
    (ls "/etc")
    (ls (os-getenv "HOME"))
    (define $elkdir (string-append (os-getenv "HOME") "/elk"))
    (ls $elkdir)

    (dolist ($file (os-glob "*.c"))
        (ls "-l" $i))           ; do `ls -l' on *.c
\end{verbatim}

\subsection{Shell Examples}
Several examples of small Elk Shell files will be given.

\subsection{Example - Delete Empty Files}
\begin{verbatim}
  (define (delete-if-empty file) 
    (if (eqv? (os-filesize file) 0)
      (os-delete-file file)))
    
  (map delete-if-empty (os-glob "*.*"))
\end{verbatim}


\subsection{Example - diffdir}

A shell to compare selected files against similarly named files
in another directory:
\begin{verbatim}
    #! /usr/local/pub/bin/elk
    ;; diffdir.esh - compare files to those in another directory
    
    (load "shell.e")            ; load declare-shell feature
    (declare-shell diff)
    
    (define $clargs (cdr (command-line-args))) ; skip arg0 
    (set! $clargs (reverse $clargs))           ; reverse
    (define $dir (car $clargs))         ; get last arg = directory
    (set! $clargs (cdr $clargs))        ; skip directory
    
    (dolist ($file $clargs)             ; loop over files
        (print $file)                   ; print filename
        (diff $file (string-append $dir "/" $file)) ; do diff
    )
    (exit 0)                            ; exit
\end{verbatim}
This shell might be called as
\begin{verbatim}
    diffdir.esh *.c ../oldversion
\end{verbatim}
The first define skips the first argument, which is the program name.
Global variables have been named \$var, resembling shell variables.
This is just a naming convention: Scheme variables can include
characters such as {\tt \$,*,-,\%,! }.

Some corresponding Bourne shell code is:
\begin{verbatim}
    #! /bin/sh
    
    for file in $clargs do ;
        echo $file ;
        diff $file $dir ;
    done
\end{verbatim}
but this example is missing the argument parsing necessary to 
extract the last command line argument and put it in the variable \$dir.

\subsection{Example - renamestar}

This shell renames a number of files, replacing a substring.
For example, 
\begin{verbatim}
    renamestar.esh "*.csh" .csh _csh
\end{verbatim}
will rename all *.csh files to *\_csh.
Note that it is necessary to quote the file pattern ``*.csh''
since it is expanded by the Elk shell, not the calling shell
(this makes the Elk shell's argument parsing easier--
the old and new name substrings are always in the \$2 and \$3 arguments).
Renamestar:

\begin{verbatim}
    #! /usr/local/pub/bin/elk
    (load "clargs.e")                   ; bind arguments to $1,$2,etc
    
    (when (not $3)
          (print "renamestar.esh <*file*> <substring> <replace>")
          (print "renames *file* replacing substring with replace.")
          (exit 1)
    )
    
    (define files (os-glob $1))         ; list of matching files
    (define sublen (string-length $2))  ; length of substring 
    
    (dolist (file files)                ; loop over files
      (let  ((s (substring? $2 file)))  ; is substring in this filename?
        (when s                         ; if so, begin
          (let ((newname                ; newname is
                 (string-append         ; concatenation of
                  (substring file 0 s)  ; portion before substring
                  $3                    ; replacement, 
                                        ; and portion after substring:
                  (substring file (+ s sublen) (string-length file))
                 ))
                );letbinding
            (format #t "~a -> ~a~%" file newname) ; print action
            (os-rename-file file newname) ; rename it
          );let
        );when s
      );let
    );dolist
    
    (exit 0)
\end{verbatim}

The library file clargs.e binds the command line argument strings 
to the scheme variables \$1,\$2,...;
\$n is bound to '() if there is no corresponding argument.
The statement "(when \$3 ..." tests that at least three arguments
are supplied and prints an usage message if necessary.

\subsection{Example - traverse}

The library file traversedir.e contains a function \verb|traverse-p|
which walks down a directory tree, calling a supplied function
with the name of each file in the tree.
\begin{verbatim}
    (define (traverse-p path dofile)
    
        (define (traverse-p-dir path dofile)  ; helper function
          (let ((dir (read-directory path)))  ; read directory
            (format #t "traversing ~a~%" path)
            (dolist (entry dir)               ; loop over files
              (if (not (member entry '("." ".."))) ; if not .,..
                  (traverse-p                 ; recurse
                   (string-append path "/" entry)
                   dofile))
            );dolist
          );let
        );traverse-p-dir

      ;; begin traverse-p function
      (if (equal? 'regular (file-status path))
    
          (dofile path)
    
          ; else not regular file - a link or directory
          (if (file-exists? path)       ;do not try to read nonexistent links
          (traverse-p-dir path dofile)) ;descend into directory
      )
    );traverse-p
\end{verbatim}
This simple function permits the construction of shells 
with tasks similar to find(1), as well as directory management
tasks which are not easy to accomplish in find.

For example, this shell deletes core files from the home directory tree:
\begin{verbatim}
    #! /usr/local/bin/elk
    (load "traverse.e")

    (define (delete-if-core fname)
      (if (equal? fname "core") (os-delete-file fname)))

    (define $HOME (os-getenv "HOME"))

    (traverse-p $HOME delete-if-core)
    (exit 0)
\end{verbatim}

\subsection{Example - fileswhen}

This subroutine uses traerse to finds all files created 
between two specified dates.
It prints a list of such files sorted by date:
\begin{verbatim}
    (load "traverse.e")
    ;; print time-sorted names of files created between two dates
    (define (fileswhen after before)
      (if (not (bound? 'sort))
          (load "sort.scm" (global-environment)))
      (let ((matches '())
        (tmin (os-parsetime after))
        (tmax (os-parsetime before)))
        (if (or (= 0 tmin) (= 0 tmax))
        (error 'fileswhen "bad time"))
        (traverse "."
          (lambda (i)
            (let ((t (os-filemodtime i)))
              (when (and (>= t tmin) (<= t tmax))
                    (set! matches
                        (cons (list t (string-append (os-getwd) "/" i))
                              matches))
              );when
            );
          );lambda
        );traverse
        (set! matches (sort matches (lambda (a b) (> (car a) (car b)))))
        (dolist (i matches)
            (format #t "~a      ~a~%" (cadr i) (os-timestring (car i))))
      matches);let
    );fileswhen
\end{verbatim}

\subsection{Example - checksumdir}

This shell walks down the directory tree, calls a checksum function for 
each file, saves this checksum in a list, compares the checksum
to a previous list, and sends the user mail reporting any
altered, new, or deleted files.
This shell illustrates some additional shell functions, 
for example, popen is called to send a mail report to the user.

More importantly, this shell dynamically loads a C function
\verb|checksum()| which computes the file checksum.  {\em
Since the checksum is then intrinsic to the shell, 
it runs much faster than an external process which would need
to be invoked for each file.}
Depending on the size of the directory, you may need to 
use a larger heap size in Elk in order to run this shell.

\begin{verbatim}
#! /usr/local/pub/bin/elk
;; checksum check a specified directory tree:
;; checksums all files, writes results to a file checksum-list.e,
;; looks for matching names in previous version of the same file,
;; reports any changed checksums, deleted files, or new files.
;;
;; The file checksum-list.e is kept in the top directory of the tree
;; and should not be deleted or write-protected.

(load "clargs.e")                       ;bind arguments to $1,...
(load "traversedir.e")

(define checksum-dir "/u/zilla/checksum/")
(define report-deleted? #t)

(if (not (bound? 'checksumfile))        ;load C function
    (load (string-append checksum-dir "checksum.o"))
)

(define old-checksum-list '())

;;;;;;;;;;;;;;;; helper functions


        ; write checksums to file
        (define (output-list path checksum-list)
          (call-with-output-file
              "checksum-list.e" ; write in current directory
            (lambda (f)
              (format f "(set! old-checksum-list '(~%")
              (dolist (i checksum-list)
                      (format f "~s~%" i))
              (format f "))~%")
            )
          )
        );output-list


        ; if differences, send mail about them
        (define (mail-report report newfiles oldlist newlist)
          (let ((f (os-popen
                 (format #f "/usr/ucb/mail -s CHECKSUM ~a" (os-getenv "USER"))
                 "w")))
            (format f "checksum at ~a~%" (os-timestring (os-curtime)))
            (dolist (i report) (format f "~a" i))
            (if report-deleted?
              (dolist (i oldlist)
                 (when (not (assoc (car i) newlist))
                     (format #t "DELETED ~a~%" (car i)) ; not reported before
                     (format f "DELETED ~a~%" (car i)))
            ))
            (dolist (i newfiles) (format f "~a" i))
            (os-pclose f)
          )
        );mail-report


(define (checksum path)
  (set! shell-verbose? #f)
  (os-chdir path)
  (if (file-exists? "checksum-list.e")
      (load "checksum-list.e"))
  (let ((checksum-list '())
        (report '())
        (newfiles '())
        (deleted-files '())
        )
    (traverse-p path
      (lambda (f)
        (let ((c (checksumfile f))
              (a (assoc f old-checksum-list))
              )

          (set! checksum-list (cons (list f c) checksum-list))

          (cond

           (a (if (not (equal? c (cadr a)))
                  (let ((msg
                         (format #f "CHECKSUM DIFFERS ~a ~a ~a~%"
                                 f c (cadr a))))
                    (print msg)
                    (set! report (cons msg report))
                  )
              )
           );a

           ((not a)
            (let ((msg (format #f "~a IS NEW~%" f)))
              (print msg)
              (set! newfiles (cons msg newfiles))
            ))

          );cond
        );let
      );lambda
    );traverse

    (output-list path checksum-list)

    (if (> (length report) 0)
        (mail-report report newfiles old-checksum-list checksum-list))
  );let
);checksum

(checksum $1)
(exit 0)
\end{verbatim}

The C function loaded by the checksum shell is listed
in the tutorial section on the foreign function interface.


\subsection{Different Architectures, Same File System}

The Unix shell interpreter mechanism specifies an absolute path, e.g.,
\begin{verbatim}
    #! /usr/local/bin/elk
\end{verbatim}
This can be a problem if machines of several different architectures
share one filename space---a shell which uses the path for one 
architecture will fail to run on other architectures.
Ideally, the bin directory containing Elk should have the same name
on each machine but should refer to different areas
for each architecture.
If this is not possible, the following horror can preface an Elk
shell file intended to run on any architecture:
\begin{verbatim}
    #!/bin/csh -f
    ;exec ${ELKBIN}/elk $0 $*
    (define .... ; elk shell commands follow
\end{verbatim}
ELKBIN is a shell variable set to the directory containing elk on
each architecture.  Note that the semicolon is necessary--this header
is read twice: once by csh, and once by elk.

\subsection{os- Routines}

Shell releated functions are consistently named with the prefix \verb|os-|
(recall that you can easily rename functions in scheme).
The command \verb|(apropos "os-")| prints a list of these functions:

\begin{verbatim}

os-fopen                ; buffered i/o - see fopen(3)
os-fclose
os-fseek
os-ftell
os-fread
os-fwrite

os-sh                   ; same as the Elk 'system' function
os-csh                  ; like os-sh, but uses csh

(os-exec "cmd")         ; executes a shell command, returns a
                        ; pid that can be passed to os-waitpid
(os-waitpid pid)        ; wait for process number pid to finish,
                        ; return the exit status of the process.
                        ; Note-the arguments are not the same as waitpid(3).

os-popen                ; see popen(3)
os-pclose               

os-getenv
os-setenv               ; environment variables are
os-unsetenv             ; passed to child processes

os-getpid
os-getppid              ; get process id of parent
os-killpg               ; kill a process group
os-killppg              ; kill parent's process group
os-killall              ; kill all your processes on this machine

os-sleep
os-curtime              ; return current time as integer
os-filemodtime          ; return file modification time integer
os-fileacctime          ; return file access time integer
os-timestring           ; convert time integer to human-readable string

os-filesize             ; return size of a file in bytes
os-filedirp             ; true if file is a directory

os-hostname             ; returns the result of gethostname(2)
os-architecture         ; returns  "mips" or "sparc"

os-delete-file          ; these are builtin - less overhead
os-rename-file          ; than starting a separate process
os-chmod
os-make-directory
os-getwd
os-stat                 ; scm/fstruct.e is an example of calling
                        ; routines like stat(2) that expect a structure

(os-pathgetext "path")  ; return extension: /a/b.c -> c
(os-pathdelext "path")  ; delete extension: /a/b.c -> /a/b
(os-pathgetpath "path") ; return path portion: /a/b.c -> /a
(os-pathgetname "path") ; return name portion: /a/b.c -> b.c

(os-uniqnam "prefix")   ; return a string (to be used as a filename)
                        ; that is unique across processes and hosts
                        
(os-glob "file*")       ; returns a list of filename strings matching
                        ; the file pattern

os-malloc               ; returns the pointer to the area *as an integer*
os-free

These functions from the Elk library are given alternate names using
the os- convention (i.e., standard Elk contains a function read-directory):

os-read-directory       ; returns a list of files in a directory
os-file-status          ; returns 'directory or 'regular
os-file-exists?

\end{verbatim}



\section{Programming with the Foreign Function Interface}

The Elk implementation of Scheme is designed to allow programs to be
written in mixtures of Scheme and C, as appropriate.  It provides
linking of compiled C object files at run-time (dynamic linking),
and C code can export new data types to Scheme.  Interfacing C to Elk
is described in the file ex.ms in the Elk doc/ directory.

In standard Elk, each C routine which will be callable from Scheme
must be interfaced to Scheme with a short wrapper or glue function.
This function is typically 5-10 lines long and is easy to write.
If one is trying to interface to a large library such as X windows or SGI's GL
library, the glue functions represent some amount of work simply due to the
large number of entries.

The foreign function interface allows {\em some} C functions to be interfaced
in a single call or table entry, eliminating the need to write a glue
function.  For example, getenv can be exported to Scheme with the call:
\begin{verbatim}
    Define_Foreign("getenv",getenv,"SRS");
\end{verbatim}
rather than using a glue routine like
\begin{verbatim}
    static Object P_Getenv (e) Object e; {
        register char *s;
        Object ret;
        Declare_C_Strings;

        Make_C_String (e, s);
        ret = (s = getenv (s)) ? Make_String (s, strlen (s)) : False;
        Dispose_C_Strings;
        return ret;
    } /*getenv*/
\end{verbatim}

It is possible to write C libraries that can be called from Scheme
and that can also be used as normal C libraries; 
see the section "Foreign Libraries".

After a function is defined
it can be called normally from Scheme, for example,
\begin{verbatim}
    (getenv "TERM") => "xterm"
\end{verbatim}

The arguments to Define\_Foreign are the name of the function in Scheme 
(which might be chosen to conform more to scheme-like naming conventions, e.g.,
`string-length' rather than `strlen'), the C entry point, 
and an argument description string. 
The argument description string ``SRS'' in this example means 
String,Returns String.  Argument description strings consist of:
\begin{verbatim}
        B       Scheme boolean <-> C int 0 or 1
        I       integer
        F       double (or float; see below)
        f       float
        S       string (char *)
        P       port (FILE *)
        A       foreign array (see below)
\end{verbatim}
The libm entry pow() would be declared,
\begin{verbatim}
    Define_Foreign("pow",pow,"FFRF");
\end{verbatim}
i.e. pow() takes two doubles and returns a double.


Scheme {\em ports} are passed to C functions as \verb|FILE *| variables.
Scheme Booleans are passed to C as the integers zero or one.
Functions which return \verb|char *| result in the creation of a Scheme
string (allocated on the Scheme heap).  This works correctly for
C functions such as \verb|getenv| which return a pointer to a statically
allocated string.
Routines which return a pointer to a string allocated with \verb|malloc|
result in a memory leak however
(the allocated string is copied and again allocated);
such functions need a wrapper function if the memory leak is to be prevented.

\subsection{Function Tables}

A number of functions can be declared at once using a foreign function
table.
\begin{verbatim}
        #include <zelk.h>
  
        static struct fordef fortab[] = {
                { "pow", pow, "FFRF" },
                { "getenv", getenv, "" },
                /* etc */,

                /* end the table with this */
                { (char *)0, 0, (char *)0 }
        };
        ....

        Define_Fortab(fortab);
        ...
\end{verbatim}



\subsection{Foreign Libraries}

There are several ways of initiating the definition of foreign functions.

A file containing foreign functions can be statically linked into 
the Elk kernel.
In this case it should have an initialization routine which calls
  {\tt  Define\_Foreign() } or {\tt Define\_Fortab() }
to export the foreign functions to elk.
This initialization routine should be called from 
\begin{verbatim}
    Init_Everything()
\end{verbatim}
in main.c; edit main.c to do this.

Alternatively, the foreign code can be kept in a separate .o file
and loaded like \verb|(load "file.o")|.
The Elk dynamic loader calls any routines in file.o which begin with
\begin{verbatim}
    init_...
\end{verbatim}
so the file's initialization routine will be automatically called
if it is named {\tt init-underbar-something}.

Unfortunately a file containing such an initialization routine cannot then be
linked with an ordinary C program, because the initialization calls 
\begin{verbatim}
    Define_Foreign() / Define_Fortab()
\end{verbatim}
will result in undefined references.

The `foreign library' approach allows code to be written so that it can be 
linked in both ordinary C programs and in Elk.
Use the following template in writing such a file:
\begin{verbatim}
        #include <rtlpkg.h>  /* do not include zelk.h */
        
        /* preface each routine with a foreign link define */
        #define LINK_mysub { "mysub", mysub, "S" } ,
        
        /* a sample routine */
        void mysub(char *s) {
          printf("called mysub with %s\n",s);
        }
        
        /* at the end of the file, a table of all foreign links */
        struct fordef fortab {
          LINK_mysub            /* gather all the link definitions */
          0                     /* indicate end of table */
        };
        
        /* package structure */
        global FORPKG0 pkg_myfile = {
            0,                                  /*packagetype. 0=current*/
            (int (*)())0,                       /*init_*/
            0,                                  /*stab,*/
            (struct fordef *)ftab,              /*ftab, put the table here*/
            (struct fordef_usage *)0            /*futab,*/
        };

        /* a function named PKGrtn_XX returns 
         * the address package structure */
        FORPKG0 *PKGrtn_My() { return &pkg_My; }
\end{verbatim}
In this approach, when a .o file is dynamically loaded,
any routines named \verb|PKGrtn_XX| are called.
These routines should return a pointer to the package structure table.
The foreign table mentioned in this structure is then passed
to \verb|Define_Fortab| in order to link the foreign routines to scheme.
There are no calls to the Elk kernel in this approach,
and normal C programs will ignore the extra structure and \verb|PKGrtn_K|
routine.
There are extra fields in the structure that are intended for expansion and
are currently unused.


\subsection{Foreign Arrays}

Foreign arrays (farrays) are essentially a mechanism for allocating
storage from the Scheme heap for use by foreign routines.
Foreign arrays appear to Scheme as a normal datatype, i.e., they
are assigned, printed, and (if unreferenced) garbage collected like
other variables.

Foreign arrays are conventionally interpreted as
homogeneous arrays of one of the C datatypes 
\verb|char, int, float.|  
Objects of other types are mapped onto \verb|char| (byte) foreign arrays.
Arrays of \verb|double| are not currently implemented.
Foreign arrays are distinguished from Scheme vectors or arrays
in that the latter are inhomogeneous arrays of pointers to arbitrary 
data and thus cannot be passed to C without conversion.

A hypothetical example for the use of a foreign array
is a three-dimensional graphics program.
This program reads the geometry of a model from a file
into a foreign array 
using a foreign call to \verb|read| or \verb|fread|,
transforms the geometry using vector calls (described below),
and writes the transformed data to a display library.
Overall control is in Scheme, but all of the computation
except the calls is in C, and no data conversion between 
Scheme and C is required.

Foreign arrays are created as the value of the call
\begin{verbatim}
    (farray <type> <length>)
\end{verbatim}
where \verb|type| is one of \verb|'integer,'real,'string|
(\verb|string| signifies a byte array)
and \verb|length| is the number of elements in the array.

The following Scheme functions manipulate foreign arrays:
\begin{verbatim}
    (farray <type> <length>
    (farray? <farray>)
    (farray-type <farray>)
    (farray-length <farray>)
    (farray-copy <farray>)
    (farray-of <values>)
    (farray-ref <farray> <index>)
    (farray-set! <farray> <index> <value>)

    ;; These functions return a new farray of a different type:
    (farray-flt <farray>)    ; convert a byte or integer farray to float
    (farray-int <farray>)    ; convert a float or byte farray to int
    (farray-string <farray>) ; convert a float or int farray to byte

    (farray-check <farray>)  ; checks that the array beginning and end
                             ; have not been overwritten
                             ; (useful when debugging a foreign routine)
\end{verbatim}

In order to avoid adding new syntax to Scheme,
farrays are printed as
\begin{verbatim}
    (% <values >)
\end{verbatim}
and the function \verb|%| (also known as \verb|farray-of|)
returns its arguments as an farray:
\begin{verbatim}
   (define x (% 3 4 5)          ; farray of integers 
   x => (% 3 4 5)
   
   (define y (% 3.3 4. 5.))     ; farray of floats

   ; farray elements must have a single type
   (define z (% 3 4.4)) => error 
\end{verbatim}

\subsection{Passing C Structures}

The foreign function interface can directly pass data of
the following types between C and Scheme:
integers (and Scheme booleans), doubles, floats, characters, strings, 
Ports or FILE streams, and homogeneous arrays of integers, floats,
or bytes.

C structure datatypes can be exported to Scheme programs in several ways.
If the structure is important and worth some programming effort,
it is best to define a new Elk type as described in ex.ms.

In some cases it is useful to be able to hold the C structure 
in Scheme, but all manipulations on the structure are
done in existing C routines 
(and it may be desired that these manipulations be hidden from scheme).
In this case, the existing library routines can sometimes be exported
to Scheme, with the structure pointer being declared to scheme
as an integer.
Some well designed existing libraries will present this sort
of interface,
and this is one approach for new C code.

Alternatively, one can try to allocate the structure inside
a foreign array and manipulate the structure in Scheme, or
in Scheme with some help from custom C routines.
This approach has the advantage that the data will be garbage collected
automatically.  The file scm/fstruct.e contains an attempt at
a C structure manipulation package for scheme.
That file contains the following example of exporting the
stat(2) structure to scheme:
\begin{verbatim}
   (define stat-bsd     ;; stat-bsd will be analogous to a typedef
      (fstruct "stat-bsd"
         '(dev_t        st_ino)
         '(ino_t        st_dev)
         '(mode_t       st_mode)
    .... etc))

   (define (stat-modtime path)
     (define s (fstruct-make stat-bsd))  ;; allocate data given typedef
     (os-stat path (fstruct-data s))     ;; call stat
     (os-timestring (fstruct-ref s 'st_mtime)) ;; reference st_mtime slot
   )
\end{verbatim}

\subsection{Passing Floats}

In pre-ANSI C, floats were always passed to or returned from other
routines as doubles.  In ANSI C a float will be passed as a float
(not a double) if the called function has a function prototype,
and if the called function itself is declared in the new prototype style.

The current implementation of the foreign function interface 
uses the argument string character `F' for double.
The Irix4 SGI compiler obeys ANSI float-passing conventions.
The foreign function interface uses `f' to signify a float
(rather than a double) argument on the SGI.
This is not currently implemented on Sparcs (the default Sun 
C compiler is not ANSI).

\subsection{Tracing Foreign Calls}

\begin{verbatim}
    (foreign-prototype <function>)
\end{verbatim}
returns the argument string of a foreign function.

\begin{verbatim}
    (foreign-trace! #t)
\end{verbatim}
will cause the name of each foreign function to be printed
before the function is called.
This can be turned off by passing \#f to foreign-trace!.

\subsection{Example}

This is an example of a foreign routine designed to be linked
at run time.  It provides the checksum function to the directory
checksum shell listed in the Elk Shell section of this tutorial.
\begin{verbatim}
    /*% cc -c -O -I/usr/local/pub/src/elk/src -DZELK % %* */
    
    #include <theusual.h>
    #include <scheme.h>
    #include <zelk.h>
    
    static int checksum(char *path)
    {
      register int cc;
      register FILE *fin;
      register int checksum = 0;
    
      fin = fopen(path,"r");
      if (fin == NULL) {
        fprintf(stderr,"cannot open %s\n",path);
        return(-1);
      }
      while( ((cc=getc(fin))!=EOF) && !feof(fin) ) {
        checksum += cc;
      }
      fclose(fin);
      return(checksum);
    }
    
    static struct fordef ctab[] = {
      "checksumfile", (vfunction *)checksum,       "SRI",
      {(char *)0,     (vfunction *)0,         (char *)0}
    };
    
    FORPKG0 pkg_CKSM = {
        0,                                  /*packagetype. 0=current*/
        (int (*)())0,                       /*init_; unused*/
        0,                                  /*stab; unused*/
        (struct fordef *)ctab,              /*ftab; required field*/
        (struct fordef_usage *)0            /*futab; for future use*/
    };

    FORPKG0 PKGrtn_cksm() { return &pkg_CKSM; }
\end{verbatim}

\section{Vector Scheme}

Many scientific and multimedia algorithms have significant
or overwhelming `data parallelism', meaning that the
same operation is applied across many pixels, 
sound samples, or other data.
In contrast to the identification of parallelism
in a compiler or in a typical AI program,
data parallelism is very easy to identify.

Such parallelism can be `exploited' in a language 
where primitive functions operate directly on the
aggregate data, rather than on one datum at a time.
Such primitive functions can be mapped directly onto vector
or certain parallel hardware.

A subset of APL-like vector operations has been added to Elk Scheme.
These include scans, reductions, gather/scatter/subscripting, 
reshaping, and some mathematical functions.
Since the functions are written in C, the performance overhead
of Scheme is diluted by the size of the vectors.
In some simple benchmarks, vectorized Scheme code was found
to be $1/5 \ldots 1/3$ of the speed of the
same benchmark written in custom C code, 
and on the order of 100 times the speed of the serial version
of the algorithm in Elk.
We note that this is in the same performance range as 
current Lisp compilers, despite the fact that Elk is an interpreter.

Vector programming requires a different mind-set---a book on 
APL might be helpful.
The following references describe data-parallel lisp dialects
for the Connection Machine;
they provide modern theoretical motivations for vector programming:
  G. Blelloch, {\em Vector Models for Data-Parallel Computing}, 
MIT Press, 1990,
  G. Sabot, {\em The Paralation Model: 
Architecture-Independent Parallel Programming}, 
MIT Press, 1988.

\subsection{Vector Expression Compiler}

Rather than overloading functions with vectors (as in APL), 
a new form \verb|parlet| (data parallel let) was added which compiles
serial code in its body onto the vector operations.
One motivation for this approach is that the \verb|parlet|
form serves to identify vectorized code in the program.
A second motivation is that the APL approach is difficult to 
compile because the scalar/vector (scalar meaning non-vector) 
nature of a variable is determined at run-time.
While Elk is interpreted,
we wanted to write code which could also be compiled using an
appropriate redefinition of \verb|parlet|.
The \verb|parlet| form declares all vector variables and
all unknown vector functions.
The \verb|parlet| form resembles the \verb|elwise| form used
in Paralation Lisp; both forms are unusual for Lisp-like languages
in that they make a type distinction explicit.

The syntax of \verb|parlet| is 
\begin{verbatim}
  (parlet <declarations> <body>)
\end{verbatim}
As a simple example,
\begin{verbatim}
  (parlet (v) 
    (= v 1))
\end{verbatim}
declares \verb|v| to be a vector and returns the result of comparing 1
to each element of this vector.
\verb|Parlet| determines the vector/scalarness of each expression
and elevates all scalar components of a mixed expression to vector
form.  Scalar functions are replaced by the corresponding vector
operators if appropriate.
Thus, the previous example expands to 
\begin{verbatim}
  (v-eq v (v-distribute 1 v))
\end{verbatim}
All vector operators are functional, though \verb|set!| can be used
to assign vectors to variables inside a \verb|parlet|.
The scalar-to-vector expansion happens at the time the 
function is defined, not at run time.
Writing scalar code in the body of the \verb|parlet| 
enhances the readability of the code, particularly for those
who are not familiar with APL and similar languages.

\subsection{Vector Coding Examples}

\subsection{Simple Examples}
\begin{verbatim}

  (define x (v-rnd 10))          ; random numbers in 0..1

  (define x (v-- (v-* 2. x) 1.)) ; scale into -1..1

  ;; The arithmetic functions v-+,v--,v-*,v-/ automatically elevate
  ;; scalar quantities (such as the constants 1,2 above) to vectors.
  ;; Without this feature, the preceding example could have been written:
  ;;
  (define x (v-- (v-* (v-distribute 2. x) x)
                 (v-distribute 1. x)))
  
  ;; parlet makes this example easier to read
  ;;
  (parlet ((x (v-rnd 10)))      ; bind x to random vector
    (- (* 2. x) 1.))            ;  scale into -1..1 
    
  ;; v-select is the vector equivalent of an 'if'.  Unlike an if,
  ;; both branches are evaluated; the condition just selects
  ;; elements from the two vectors resulting from evaluating the branches.
  ;;
  ;; This code returns a vector in which any negative numbers in x
  ;; are replaced by -1:
  ;;
  (v-select (v-ge x (v-distribute 0. x))
            x
            (v-distribute -1. x))

  ;; the same code expressed with parlet:
  ;; x appears in the binding to declare it as a vector)
  ;; (the parletv version prints the macro-expansion before evaluation;
  ;;
  (parletv ((x))
        (if (>= x 0.) x -1.))
\end{verbatim}

\subsection{Variance of a Vector}

\begin{verbatim}

;; vector version
(define (variance a)
  (let* ((len (farray-length a))
         (avg (/ (+/ a) len))
         (dev (parlet ((a)) (sqr (- a avg)))))
    (/ (+/ dev) len)
  ))

;; uses this average function
(define (sqr a) (parlet ((a)) (* a a)))


;; serial version
(define (non-vector-variance a)
  (let ((sum 0.)
        (len (farray-length a))
        (mean #f))
    (dotimes (i len)
             (set! sum (+ sum (farray-ref a i))))
    (set! mean (/ sum len))
    (set! sum 0.)
    (dotimes (i len)
             (let ((d (- (farray-ref a i) mean)))
               (set! sum (+ sum (* d d)))))
    (/ sum len)))
\end{verbatim}


\subsection{Minimum Index Benchmark}
\begin{verbatim}
;; find the index of the minimum element of an array:

;; vector version
(define (v-minindex x)
  (+/ (v-not (\\+ (v-eq x (v-distribute (v-min/ x) x))))))

;; serial version
(define (v-serialminindex a)
  (let ((min (farray-ref a 0))
        (mini 0)
        (len-1 (1- (farray-length a))))
    (for i 1 len-1
         (when (< (farray-ref a i) min)
               (set! min (farray-ref a i))
               (set! mini i))
    )
  mini))

;; timings (100 passes each)
;; Note that the speedup is greater for long vectors.
;; Vector length 2000:
;; vector:   3 secs.
;; serial: 176 secs.
;; Vector length 10:
;; vector:   0.8 secs.
;; serial:   1.7 secs.
\end{verbatim}

\subsection{Histogram Equalization}
One final example illustrates vector coding in a real program.
The program does histogram equalization on an image.
It uses a custom graphics library (GR-*); 
the various graphics calls should be fairly self-evident.

\begin{verbatim}
#! /usr/local/sgi/bin/elk
;; gr-histeq -- histogram equalization

(load "clargs.e")       ; read command-line args -> $1,$2,etc

(GR-init)                               ; init GR system

(define Bufs (GR-open $1))              ; open buffer(s)

;; mdefine in .elkrc macro-expands at read time rather than eval-time.
(mdefine (hist1 fp)
  (format #t "~a [~a,~a]~%" (GR-name fp) (GR-xres fp) (GR-yres fp))
  (let ((yres (GR-yres fp))             ; x,y resolution
        (xres (GR-xres fp))
        (htab (farray 'integer 256)))   ; histogram table
    (if (< xres 256)
        (error 'hist1 "buffer is to narrow to display histogram"))

    ;; sum pixel values into htab
    (dotimes (y yres)                   ; loop over scanlines
      (let ((buf (GR-rdrow fp y)))      ; read row->buf
        (set! htab
              (parletv ((htab)
                        (c (v-mapcount buf 0 255)))
                       (+ htab c)))
      )
    )

    ;; integrate to make cumulative grey level mapping function
    (set! htab (v-+scan htab))
    (set! htab (v-/ (v-* 255 htab) ; not 256
                    (* xres yres)))

    ;; indirect through cdf
    (dotimes (y yres)
      (let ((buf (GR-rdrow fp y)))      ; read row->buf

        (GR-wrrow fp y (v-[] htab buf)) ; write the result
      )
    )

  );let
);hist1


(dofarray (i b Bufs) (hist1 b)) ; loop over all buffers

(GR-finit)                              ; cleanup
(exit 0)
\end{verbatim}


\subsection{Vector Functions}

Elk scheme vector functions operate on foreign arrays.
Most functions operate on integer and float but not character farrays;
convert character farrays using e.g. \verb|farray-int| before use.
Scheme vector operations are currently restricted to rank of 2 or less,
and not all operations work for rank 2.
Boolean vectors are currently represented as vectors of integers;
`word parallelism' is not used yet.
The vector package extends foreign arrays to several dimensions.
Arrays are stored in column-minor order.

\subsection{Array Primitives}

\verb|(v-array-set! v idx val)|
Multidimensional accessing occurs when idx is a foreign array of integers.
The indices are in the `normal' order: 
the last element of a 2 (rows) by 3 array is (\% 1 2).
Since the index is itself an array, and due to the normal read/print order
for arrays, this means that the most major axis of the index is in [0]
and the minor axis is in the highest slot.
Idx may also be an integer, in which case this is the same as farray-set!

\verb|(v-array-ref v idx val)|
See \verb|v-array-set!|.

\subsection{Shape/Select}

\verb|(v-shape v)| => returns the length or shape of v in an int farray.
The shape of a 2 by 3 matrix is (\% 2 3).

\verb|(v-ravel v)| => returns an unraveled vector,
ie, vector containing concatenation of matrix rows or planes

\verb|(reshape array shape[ndim])| --  Give a new shape to an array.
Sometimes called restruct.
The specified shape and source length conform,
whereas in some APLs reshape wraps if needed.

\verb|(transpose array)| --  Return transpose of matrix.

\verb|(v-compress v boolvector)| => Return vector of elements of v
corresponding to ones in boolvector.
Called compress in APL, pack in [Blelloch].

\verb|(v-append v1 v2 ... )| => Concatenates the ravel of the arguments.

\verb|(v-select b v1 v2)| => select between v1,v2.
Copy v1[i] if b[i]=1, else v2[i].

\subsection{Gather/Scatter/Subscripting}

\verb|(v-mapcount v min max)| -- vector map.
Returns an array min..max which counts the number of times
a particular value appears in v. Values outside min..max
are discarded.  INTEGER ONLY!
Useful for histogram generation for example.
Similar to map primitive in Paragon.

\verb|(v-[] v p)| -- subscripting.
If p is scalar, this is equivalent to farray-ref.
If p is a vector, the corresponding elements are
returned from v (the position elements need not be unique),
and the result has the length of p.
If v is a matrix, the rows corresponding to p are returned.

\verb|(v-gather v offset stride len)|
Return a row or column of a multidimensional array,
or similar operations.
   gather[j] = source[offset + j*stride];  j=0..len-1

\verb|(v-scatter destarray offset stride len srcarray)|
Inverse of gather.
Insert a row or column into a multidimensional array,
or similar operations.
   src[j] => dest[offset + j*stride];  j=0..len-1.
NOTE THIS IS A SIDE EFFECT--DATA IS INSERTED INTO DESTARRAY.

\subsection{ Monadic Functions}
With the exceptions of v-abs and v-not, the result vectors are float.

\verb|(v-sin v)|

\verb|(v-cos v)|

\verb|(v-sqrt v)|

\verb|(v-exp v)|

\verb|(v-abs v)|

\verb|(v-rnd len)| => Returns a vector[len] of random values.
len may be another farray, in which case its length is used.

\subsection{ Dyadic Functions}
Mixed (int,float) argument types promote to float result vectors.

\verb|(v-+ a b)| --  elementwise addition.

\verb|(v-- a b)| --  elementwise subtraction.

\verb|(v-* a b)| --  elementwise multiplication.

\verb|(v-- a b)| --  elementwise division.
There is NO divide-by-zero check.

\verb|(v-min a b)| -- elementwise min.

\verb|(v-max a b)| -- elementwise max.

\verb|(v-mod a b)| -- elementwise mod, implemented as fmod().

\verb|(v-imod a b)| -- elementwise integer mod, implemented as \%.

\subsection{ Boolean Functions}
The result type is an integer vector.

\verb|(v-eq a b)|

\verb|(v-ne a b)|

\verb|(v-lt a b)|

\verb|(v-le a b)|

\verb|(v-gt a b)|

\verb|(v-ge a b)|

\verb|(v-and a b)|

\verb|(v-or a b)|

\verb|(v-not v)|

\verb|(v-xor a b)|

\subsection{ Float Dyadic Functions}
These functions always return float vectors,
rather than vectors of the highest argument type.

\verb|(v-pow a b)| -- elementwise power function

\subsection{Reductions}

\begin{verbatim}
  scalar = (op-reduce arr)
  ---------------
  scalar r = arr[0];
  for( i=1; i < len(arr); i++ ) r = op(r,arr[i]);
\end{verbatim}

\verb|(+/ v)| or v-+reduce

\verb|(-/ v)| or v--reduce

\verb|(* / v)| or v-*reduce

\verb|(min/ v)| or v-minreduce

\verb|(max/ v)| or v-maxreduce

\subsection{ Scans}
Scans use the algorithm:
\begin{verbatim}
  outvector[0] = z = vector[0];
  for( i=1; i < len(arr); i++ ) {
    z = op(z,vector[i]);
    outvector[i] = z;
  }
  return outvector;
\end{verbatim}

\verb|(\\+ v)| or \verb|v-+scan|

\verb|(\\- v)| or \verb|v--scan|

\verb|(\\* v)| or \verb|v-*scan|

\verb|(\\min v)| or \verb|v-minscan|

\verb|(\\max v)| or \verb|v-maxscan|

\subsection{ Miscellaneous}

\verb|(v-distribute value len)|
Generate a vector[len] initialized to value.

\verb|(v-emote)|
Squeeze emotional value from a vector.

\verb|(v-index len)|
Generate a vector[length] of index values.\\
(v-index 3) => (\% 0 1 2)

\verb|(v-truncate v)|
Returns integerized vector.

\verb|(v-reverse v)|
Returns v in reversed order.
Could be defined as:
\begin{verbatim}
  (define (v-reverse a)
    (let ((size (farray-length a)))
      (v-[] a (v-- (v-distribute (1- size) size) (v-index size)))))
\end{verbatim}

\verb|(v-rotate v a)|
Positive a rotates to the right:
Result[k+a]:=v[k].
This could be defined as:
\begin{verbatim}
  (define (v-rotate v n)
    (v-[] v"
      (parlet ((i (v-index (farray-length v))))
             (v-mod (+ n i) (farray-length v)))))
\end{verbatim}

\verb|(v-shift v a . fill-value)|
Result[k+a]:=v[k].
Result has same length as v.
Empty values are filled with fill-value (if provided),
or with the adjacent array element.
Eventually a boolean fill-value will specify creation of a shorter result.

\verb|(v-head v d)|
Return the vector resulting from discarding the d lowest elements of v.
\begin{verbatim}
  (v-head (% 1 2 3) 1) => (% 2 3).
\end{verbatim}


\verb|(v-tail v d)|
Return the vector resulting from discarding the d highest elements of v.
\begin{verbatim}
  (v-tail (% 1 2 3) 1) => (% 1 2).
\end{verbatim}

\end{document}
